package com.zklh.leetcode.top100;

import java.util.Deque;
import java.util.LinkedList;

/**
 * 柱状图中最大的矩形
 *
 * @version 1.0
 * @Author tongnan
 * @Date 2023/10/12
 */
public class Solution84 {
    public int largestRectangleArea(int[] heights) {
        int max = 0;
        int[] leftArea = new int[heights.length];
        int[] rightArea = new int[heights.length];
        Deque<Integer> deque = new LinkedList<>();
        deque.add(0);
        for (int i = 1; i < heights.length; i++) {
            while (!deque.isEmpty() && heights[deque.peek()] >= heights[i]) deque.poll();
            leftArea[i] = heights[i] * (i - (deque.isEmpty() ? 0 : deque.peek()+1));
            deque.push(i);
        }
        deque.clear();
        deque.add(heights.length-1);
        for (int i = heights.length-2; i >= 0; i--) {
            while (!deque.isEmpty() && heights[deque.peek()] >= heights[i]) deque.poll();
            rightArea[i] = heights[i] * ((deque.isEmpty() ? heights.length-1 : deque.peek()-1) - i);
            deque.push(i);
        }
        for (int i = 0; i < heights.length; i++) {
            max = Integer.max(max, heights[i] + leftArea[i] + rightArea[i]);
        }
        return max;
    }

    public static void main(String[] args) {
        Solution84 solution84 = new Solution84();
        int[] heights = {2,1,5,6,2,3};
        System.out.println(solution84.largestRectangleArea(heights));
    }
}